Major U.S. airlines operate up to 5,000 flights per day, and have to contend with crew recovery problems when a scheduled pairing of crew members with a sequence of flights is broken. Such broken pairings may occur when crew members do not report to work due to illness or other circumstances, restrictions on flight time are exceeded by a crew member, a flight is delayed or canceled, a flight is diverted to a different destination, a flight is added, or equipment substitutions or swaps become necessary which in turn require new crew members with different qualifications.
Crew rescheduling involves matching crews with a recovery flight schedule and acceptable fleet type as soon as possible in a cost effective way, while ensuring conformance with crew legalities such as government policies including the FARs (Federal Aviation Regulations), union contracts, and company policies.
The following published articles are of general interest: “Optimization Model and Algorithm for Crew Management During Airline Irregular Operations”, by Guo Wei, Gang Yu, and Mark Song, Journal Of Combinatorial Optimization, Kluwer Academic Publishers (1997); and “A Decision Support Framework for Crew Management During Airline Irregular Operations”, by Mark Song, Guo Wei, and Gang Yu, Operations Research In The Airline Industry, Kluwer Academic Publishers (1998).
The algorithms described in the above publications are very similar. The main features of these algorithms are their use of the space-time network model, in which problems with irregular operation can be physically represented by a network using four types of nodes and five types of network arcs. As a result of this network representation, a mathematical model can be formulated to reflect the problem at hand.
For relatively small problems (number of cities less than 10, number of pairings less than 5, number of flights less than 20), use of the model can achieve an optimal solution. If the size of a problem increases, however, a heuristic method has to be applied in order to get an acceptable solution. The heuristic methods described in these two publications are centered at the decomposition of the given problem, so that a large problem can be divided into a number of smaller problems such that each smaller problem contains exactly one open pairing.
For each smaller problem, the algorithm calls for setting up a sub-network, solving a shortest path network and using a depth-first search method to fix an open pairing. In going through each of these iterations for any normal airline irregular operation problem, the costs in terms of solving time can be very expensive and impractical to support a decision making in a real time environment.
Referring to FIG. 1, a functional block diagram of the system environment disclosed in U.S. patent application Ser. No. 09/364,156 is shown, where an Optimization Server 1 (which in the preferred embodiment is an HP K-570 running an 11.x HPUX operating system), in electrical communication with a user by way of a bi-directional communication path 2 receives a request for optimal solutions to a specific flight schedule disruption. In response to the request, the Optimization Server 1 initializes an Aircraft Optimization Engine 3 by way of a bi-directional communication path 4, and provides the Aircraft Optimization Engine 3 a filename of an Aircraft Problem Specification. The Aircraft Optimization Engine 3 accesses the Aircraft Problem Specification by way of a bi-directional communication path 8, and generates a set of optimal solutions including aircraft reassignments, rescheduling, and reroutings, to overcome the disruption. The solutions are transmitted over communication path 4, and through the Optimization Server 1 and bi-directional path 2 to the user.
The Aircraft Optimization Engine 1 in turn initializes a Crew Optimization Engine 5 by way of a bi-directional communication path 6 to determine whether optimal flight solutions are efficiently supported by flight and service crews. The Crew Optimization Engine 5, upon being initialized, receives a Crew Problem Specification from the user by way of communication path 2, Optimization Server 1, and a bi-directional communication path 7. The Crew Problem Specification includes flight records, Pairing records, and Broken Crew information records. The crew solutions generated by the Crew Optimization Engine 5 are supplied by way of the communication path 7, Optimization Server 1, and communication path 2 to the user.
During operation, the Aircraft Optimization Engine 3 and the Crew Optimization Engine 5 communicate by way of bi-directional communication paths 10 and 11, respectively, with a memory system such as disk storage unit 9 having stored therein memory objects which in the preferred embodiment are C++ objects containing all of the data used by the optimization engines to solve problems. For example, the C++ object for each flight would capture all information about a given flight. More specifically, a flight object would contain object members such as a flight's departure city, arrival city, departure time, arrival time as well as crewmembers that are assigned to this flight. The object would also contain some basic member functions that allow the engine to access these data members and set/reset them. The C++ objects in turn are created and updated by the Data Collection Unit 12 and the Data Update Unit 13, respectively. More particularly, the Data Collection Unit 12 receives flight data, Open Flight data, crew data, reserve data, pairing data and open pairing data from the user by way of bi-directional communication path 14. The Data Collection Unit 12 also creates C++ objects which are supplied by way of a bi-directional communication path 15 for storage in the disk storage unit 9, at memory locations specified by a Memory Mapping Unit 16 by way of a bi-directional communication path 17. Further, the Data Update Unit 13 receives revisions to the C++ objects from the user over a bi-directional communication path 18, and supplies corrections through a bi-directional communication path 19 to the objects identified by the Memory Mapping Unit 16.
The following data is needed for setting up the C++ database for the Crew Optimization Engine:
In an object oriented language environment, all of the flight information described above can be stored in a flight record as an object, and all of the flight records may be saved in an array structure for fast retrievals. Further, all of the crew information described above can be stored in a crew record as an object, and all the crew records may be saved in an array structure for fast retrievals.
In an object oriented language environment, all of the flight, crew, and pairing information can be stored in a pairing record as an object. Further, all of the pairing records may be saved in an array structure for fast retrievals.
The Memory Mapping Unit 16 receives control signals from the user over a bi-directional communication path 20, and in response thereto identifies the addresses of the C++ objects in the disk storage unit 9 that are being operated upon. By means of the Memory Mapping Unit 16 and the Data Update Unit 13, the user is able to keep the data stored in the Disk Storage Unit 9 current with the data being supplied to the user by way of communication path 2.
Thus, at any given time, the C++ objects of the Disk Storage Unit 9 reflect the existing flight environment, including identification of protected flights which are not to be canceled or delayed; flight sequences or routes for each aircraft; the stations or airports to be used by the aircraft; the fleets assigned to each station; station closure times; fleet arrival and departure curfews (times during which an aircraft is allowed to land and take-off); inviolable and violable maintenance schedules; aircraft seat capacities; fleet operational ground times; operations and flight disruption costs; sub-fleet disruption costs; and revenue and passenger information for each scheduled flight.
It is to be understood that Aircraft Optimization Engine 3, Crew Optimization Engine 5, and Optimization Server 1 each may be microprocessors. Further, the details for updating and formatting flight, crew, and pairing information may be found in U.S. patent application Ser. No. 09/364,156.
Problems are detected and formulated during the course of the database updates. Upon receiving each message, the system analyzes the current operations, checks for any problems, and formulates and records any problems that are detected.
Problems with open pairings are explicitly indicated by pairing update messages and crew update messages received from a user, and problems with open flights are explicitly indicated by the flight update messages. Problems with crew members, however, are detected as the result of current operation analysis.
In repairing open pairings, the above patent application introduces the use of self-connection solution components including the self directly-connected and self indirectly-connected components, skipping-leg solution components including the forward leg-skipping and backward leg-skipping components, an extended-out broken crew solution component, and swap methods including a one-way swap, a two-way swap, and a three-way swap method to cure open flights and open pairings.
A further solution component introduced by U.S. patent application Ser. No. 09/364,196 is a partial self-fix, as illustrated in FIG. 2, where a pairing represented by a flight pattern comprised of flights f1 through f4 is shown with flights f2 and f3 assumed canceled. A breaking point thus occurs at airport B. If a crew member P now located at airport B and having an original base at airport A is returned directly to the originating base A, a partial solution would result because the flight f4 would be an open flight. That is, it would not have a full crew. However, if a deadhead path DP may be used to bring the crew member P back into the original pairing beginning at airport D, a full solution referred to as an indirect self-fix would be achieved since the flight f4 would now have a full crew. As before, the crew member P is returned to the originating base A. In this case, airport D becomes a recovery point.
If in the above example, airport B and airport D are the same airport, and the crew member P's arrival time Ta at airport B is less than the departure time Td at airport D, a feasible connection is possible without use of deadhead paths or the creation of any open flights. Such a solution is referred to as a direct self-fix. A direct self-fix solution may occur in the case of a round trip (out and back) flight cancellation, or where a crew member is removed from a sequence of flights to achieve a legal status.
Where a crew member can be brought back to the original pairing by skipping flights, and possibly using deadhead paths, a partial self-fix referred to as a k-skip self-fix occurs. If the crew member cannot be rerouted back to the originating base through use of deadhead paths and skipping flights until after the release time of a duty period, however, an extended-out self-fix is said to have occurred.
Once all possible fixes for curing an open pairing are determined, the cost associated with each fix is determined, and the selection of the fix having the least cost to the airline becomes a complete self-fix.
Referring to FIG. 3, one-way, two-way, and three-way swaps with three flight patterns or pairings (P1, P2, and P3) are illustrated. Assume that flight f12 of P1 and flight f23 of P2 have been canceled as represented by the “x”. The crew members of flight f11 may fly a deadhead path D11 to crew flight f24 of P2, and then fly a deadhead path D22 to reassume their duties in P1 beginning with flight f15. If the crew of flight f12 can avail themselves of a self-fix, whether a Partial Self-Fix or a Complete Self-Fix, by flying the Deadhead Path Dx to crew flight f25 and thereby resume their duties in P2, then the irregularities of both P1 and P2 are cured. The above process is referred to as a one-way swap. Since flights f13 and f14 are left open without a crew, however, such a solution may be too costly for an airline.
Further assume that flight f23 of P2 is canceled, and that the crew of flight f22 of P2 is flown by deadhead path D21 to crew flights f13 and f14 of P2, and thereafter return by deadhead path D12 to their original pairing P2. A complete solution for pairing P1 thus results since no flights except canceled flight f12 of the pairing P1 are skipped. The above two processes taken together, where flights are taken from one pairing to cure the first, and from the first to cure the second, constitute a two-way swap. Flights f24 and f21 of pairing P2, however, would be left open as they would be without a crew. The cost to the airline would include the deadhead costs as well as the cost of the open flights in P2.
If in the process of curing the pairing P2 flights are taken from pairing P3 rather than pairing P1, and thereafter flights are taken from pairing P1 to cure pairing P3, a three-way swap results. For example, the crew from flight f22 of P2 may fly deadhead path D23 to crew flight f34 of P3, and thereafter fly deadhead path D32 to reassume their original pairing with flight f26. The crew of flight f33 of P3 then may fly deadhead path D31 to crew flight f14 of P1, and thereafter fly deadhead path D13 to return to their original pairing P3 by crewing flight f36. In this scenario, flight f13 of P1, flight f25 of P2, and flight f3, of P3 would be left open or skipped. The airline again would assume the costs of the deadhead paths and the open flights left after the three-way swap.
The problem thus is solved by determining which of the available solutions is least costly to the airline.
The above methods as presented in U.S. patent application Ser. No. 09/364,156 are limited in the number of pairings which may be called upon to provide solutions, and are subject to a condition where due to the limited resources, deadhead paths may not be available to effect a one-way, two-way, or three-way swap. No facility for providing high order n-way swaps (where n is an integer greater than 3) as a solution component is disclosed. Further, as in the example illustrated by FIG. 3 above, a three-way swap may prove too costly to an airline. A further deficiency in the above system is that with an ever increasing need for more rapid solution generation, improvements over decision tree selection processes, and depth-first-search and shortest-path algorithms is needed.
The present invention provides plural solutions in near real time through two solution paths without need for decision tree selection processes, depth-first-search, or shortest path algorithms, and enlarges the solution domain through the addition of a new solution component, one-way-fix, to include all pairings of an airline in the solution process. N-way swaps thereby become a solution component, and the likelihood of generating a solution which meets the so-called legality rules imposed by airlines, collective bargaining contracts, flight regulations, and other parameters such as costs, is raised to a near certainty.